package com.dbh.alg.algorithm.hot100.滑动窗口;

import java.util.HashMap;
import java.util.Map;

public class Leetcode3_无重复字符的最长子串 {

    public int lengthOfLongestSubstring(String s) {
        // 创建一个哈希表来存储字符上次出现的位置
        Map<Character, Integer> lastOccurred = new HashMap<>();
        // start表示当前无重复子串的起始位置
        int start = 0;
        // maxLength记录最长无重复子串的长度
        int maxLength = 0;
        // 遍历整个字符串
        for (int i = 0; i < s.length(); i++) {
            // 获取当前位置的字符
            char ch = s.charAt(i);
            // 检查当前字符是否曾经出现过，并且该字符的上次出现位置在当前子串范围内
            if (lastOccurred.get(ch) != null && lastOccurred.get(ch) >= start) {
                // 如果出现过且有效范围内，则将其实位置移到该字符上次出现位置的右边一位
                start = lastOccurred.get(ch) + 1;
            }
            // 计算当前子串的长度并更新最大长度
            if (i - start + 1 > maxLength) {
                maxLength = i - start + 1;
            }
            // 更新当前字符串的最新出现位置
            lastOccurred.put(ch, i);
        }
        // 返回最长无重复子串的长度
        return maxLength;
    }

}
